209A - Multicolored Marbles - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1e9+7;

int main(){
    ios::sync_with_stdio(0), cin.tie(0);

    int n; cin>>n;
    vector<vector<ll>> dp(n+1,vector<ll>(2));
    dp[1][0]=0, dp[1][1]=1;
    for(int i=2; i<=n; i++){
        if(i%2){
            dp[i][0]=dp[i-1][0];
            dp[i][1]=dp[i-1][0]+dp[i-1][1]+1;
        }
        else{
            dp[i][1]=dp[i-1][1];
            dp[i][0]=dp[i-1][1]+dp[i-1][0]+1;
        }
        dp[i][0]%=MOD, dp[i][1]%=MOD;
    }
    cout<<(dp[n][0]+dp[n][1])%MOD;
}